/*
 * @lc app=leetcode.cn id=210 lang=cpp
 *
 * [210] 课程表 II
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
    struct Node
    {
        int course;
        set<int> father; //先修课程
        set<int> next;   //需要在此课程之后学习的课程
        Node(int course) : course(course) {}
    };
    vector<Node *> nodes;

public:
    void eraseLearnedCourse(Node *n, vector<int> &ans)
    {
        //先将已经学习过的课程从先修课程中删除
        for (auto i : ans)
        {
            if (n->father.empty())
                break;

            n->father.erase(i);
        }
    }

    bool dfs(Node *n, vector<bool> &visited, vector<int> &ans)
    {
        visited[n->course] = true;
        eraseLearnedCourse(n, ans);
        for (auto f : n->father)
        {
            if (visited[f])
            {
                // f被访问过，且f没有在ans中，说明 f 无法完成
                if (nodes[f]->father.empty() == false)
                    return false;
                else
                    continue;
            }
            if (!dfs(nodes[f], visited, ans))
                return false;
        }
        eraseLearnedCourse(n, ans);
        if (n->father.empty())
        {
            ans.push_back(n->course);
            return true;
        }
        return false;
    }

    vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites)
    {
        nodes = vector<Node *>(numCourses, nullptr);

        for (const auto &p : prerequisites)
        {
            int c1 = p[0], c2 = p[1];
            if (nodes[c1] == nullptr)
            {
                nodes[c1] = new Node(c1);
            }
            if (nodes[c2] == nullptr)
            {
                nodes[c2] = new Node(c2);
            }

            nodes[c1]->father.insert(c2);
            nodes[c2]->next.insert(c1);
        }

        vector<int> ans;

        vector<bool> visited(numCourses, false);
        for (int c = 0; c < numCourses; c++)
        {
            if (visited[c])
                continue;
            if (nodes[c] == nullptr)
            {
                ans.push_back(c);
                visited[true];
            }
            else
                dfs(nodes[c], visited, ans);
        }

        if (ans.size() == numCourses)
            return ans;
        else
            return {};
    }
};

// int main()
// {
//     int numCourses = 3;
//     vector<vector<int>> pre = {
//         {0, 1}, {0, 2}, {1, 2}};
//     Solution().findOrder(numCourses, pre);
//     return 0;
// }

// @lc code=end
